#
# avltree.pl : ＡＶＬ平衡木（二分探索木を継承）
#
#
use Bintree;

package Avltree;
@ISA = (Bintree);

# $nil の取得
sub make_tree {
  $nil = Bintree->make_tree();
  bless $nil, 'Avltree';
  $nil;
}

# 節を作る
sub new {
  my ($type, $item) = @_;
  my $obj = {
    'item'    => $item,
    'left'    => $nil,
    'right'   => $nil,
    'balance' => 0
  };
  bless $obj, $type;
  $obj;
}

# データの追加
sub insert_tree {
  my ($root, $item) = @_;
  my @stack = ();
  my $place = \$root;
  while( $$place != $nil ){
    my $node = $$place;
    my $result = $item->compare( $node->{'item'} );
    push( @stack, $node );
    if( $result == 0 ){
      return $root;       # 同じデータ有り
    } elsif( $result < 0 ){
      $place = \$node->{'left'};
    } else {
      $place = \$node->{'right'};
    }
  }
  # データの挿入
  my $obj = Avltree->new($item);
  return $obj if $root == $nil;  # ルートに挿入
  $$place = $obj;
  &check_balance( $root, $obj, \@stack );
}


# バランスのチェック
sub check_balance {
  my ($root, $node, $stack) = @_;
  my $cnode = $nil;
  my ($b, $pnode);

  for( ; @$stack > 0; $node = $pnode ){
    $pnode = pop( @$stack );
    if( $pnode->{'left'} == $node ){
      $b = ++$pnode->{'balance'};
    } else {
      $b = --$pnode->{'balance'};
    }
    return $root if $b == 0;    # 書き換え必要無し
    if( $b > 1 ){
      $cnode = &LR_rotate( $node, $pnode );
      last;
    } elsif( $b < -1 ) {
      $cnode = &RL_rotate( $node, $pnode );
      last;
    }
  }
  # 子の付け替え処理
  if( @$stack > 0 ){
    my $ppnode = pop( @$stack );
    if( $ppnode->{'left'} == $pnode ){
      $ppnode->{'left'} = $cnode;
    } else {
      $ppnode->{'right'} = $cnode;
    }
  } elsif( $cnode != $nil ){
    # ルートの変更
    return $cnode;
  }
  $root;
}

# LR 回転
sub LR_rotate {
  my ($node, $pnode) = @_;
  my $cnode;

  if( $node->{'balance'} < 0 ){
    # LR2
    $cnode = $node->{'right'};
    $pnode->{'left'} = $cnode->{'right'};
    $node->{'right'} = $cnode->{'left'};
    $cnode->{'right'} = $pnode;
    $cnode->{'left'} = $node;
    if( $cnode->{'balance'} > 0 ){
      $pnode->{'balance'} = -1;
      $node->{'balance'} = 0;
    } elsif( $cnode->{'balance'} < 0 ){
      $pnode->{'balance'} = 0;
      $node->{'balance'} = 1;
    } else {
      $pnode->{'balance'} = 0;
      $node->{'balance'} = 0;
    }
    $cnode->{'balance'} = 0;
  } else {
    # LL1
    $pnode->{'left'} = $node->{'right'};
    $node->{'right'} = $pnode;
    $pnode->{'balance'} = 0;
    $node->{'balance'} = 0;
    $cnode = $node;
  }
  $cnode;
}

# RL 回転
sub RL_rotate {
  my ($node, $pnode) = @_;
  my $cnode;

  if( $node->{'balance'} > 0 ){
    # RL2
    $cnode = $node->{'left'};
    $pnode->{'right'} = $cnode->{'left'};
    $node->{'left'} = $cnode->{'right'};
    $cnode->{'left'} = $pnode;
    $cnode->{'right'} = $node;
    if( $cnode->{'balance'} > 0 ){
      $node->{'balance'} = -1;
      $pnode->{'balance'} = 0;
    } elsif( $cnode->{'balance'} < 0 ){
      $node->{'balance'} = 0;
      $pnode->{'balance'} = 1;
    } else {
      $node->{'balance'} = 0;
      $pnode->{'balance'} = 0;
    }      
    $cnode->{'balance'} = 0;
  } else {
    # RR1
    $pnode->{'right'} = $node->{'left'};
    $node->{'left'} = $pnode;
    $pnode->{'balance'} = 0;
    $node->{'balance'} = 0;
    $cnode = $node;
  }
  $cnode;
}


1;

# end of file
